nLab combinatorial design

Combinatorial design is a generic term for combinatorial structures described by families of finite sets satisfying some symmetries or other combinatorial properties of mutual arrangement. For example, the block designs generically describe a set with family of subsets satisfying some combinatorial properties.

A concrete structures of this kind are block $t$-designs: if $t$ is an integer a $t$-design is a set $X$ with a family of $k$-element subsets of $X$ (called blocks) such that every $x\in X$ appears in exactly $r$ blocks, and every $t$-element subset $T$ appears in exactly $\lambda$ blocks. One also says $t-(v,k,\lambda)$-design if $v$ is the cardinality of $X$. The number of blocks $b$ and $r$ are determined by the other data. The applications include algebraic codes, finite geometries, algorithm design etc.

(Non)existence of combinatorial designs with specific properties often has profound consequences on classification of various other mathematical structures (not necessarily finite ones); in particular lattices, finite geometries, finite groups etc.

Literature

Related $n$Lab items: binary linear code, synthetic projective geometry, Joyal species, matroid, building, incidence geometry

• wikipedia: combinatorial design
• Handbook of Combinatorial Designs, CRC Press 2006
• P. Dembowski, Finite geometries, Springer-Verlag 1968
• Jens Zumbrägel, Designs and codes in affine geometry, arXiv:1605.03789
• Peter Keevash, The existence of designs, pdf

We prove the existence conjecture for combinatorial designs, answering a question of Steiner from 1853. More generally, we show that the natural divisibility conditions are sufficient for clique decompositions of simplicial complexes that satisfy a certain pseudorandomness condition.

category: combinatorics